Due to the ever increasing size of application programs, modern operating systems use the concept of virtual memory management in order to considerably extend the visible size of a computing device's random access memory (RAM), in the following also referred to as “main memory” or “primary memory”, by backing the RAM with a storage area of a further memory referred to as “auxiliary memory” or “secondary memory” on a permanent (non-volatile) storage device called “swap device”, such as, e.g., a hard-disk drive or a USB memory stick. This swapping process thereby allows multitasking systems to run a multiplicity of time-sliced processes on the computing device. For example, an active process running on said computing device can be given access to the entire virtual address space accessible by a data processing unit of said computing device. Idle processes can be swapped out to said secondary memory and kept ready to run when their turn arrives again. The virtual address space that can be accessed by this data processing unit is typically divided into page frames, and a translation mechanism is applied to convert virtual address references issued by a running process to a physical page which contains instructions or contents data required by the process. When an operating system runs low on physical pages, pages which have not been used in the recent past can be written to the above-mentioned swap device. Newly available page frames can then be supplied to active processes. When a page frame cached on the swap device is required at a later time by a process, a page fault occurs and the data has to be fetched back from the swap device. The problem is that the throughput for applications whose working set size does not fit in said primary memory degrades significantly owing to an increase in the number of page faults. Disk access latencies are usually of the order of tens of milliseconds, which is much longer than memory access time, the latter being typically of the order of several tens or hundreds of nanoseconds. Hence, recent research has proposed compressing memory pages in preference to swapping them out to disk. This hides long latencies associated with a disk access because a page has to be merely decompressed when a page fault occurs. Such a compressed memory system, in the following also referred to by the generic term “memory management system”, can be implemented in various ways, including software approaches, such as, e.g., modifications of the operating system kernel, and hardware implementations, such as, e.g., compressed cache lines. The former approach requires access to the kernel source code and thus may not be easily ported across different operating systems. A hardware implementation, on the other hand, may add to the cost of the computing device.
As described above, virtual memory management techniques can be applied to expand an application's view to the main memory of a computing device, but it can also be used to virtually execute an application program's machine code directly from a memory module integrated in or connected to said computing device, e.g., a hard-disk drive or a USB memory stick, which otherwise does not permit direct execution of program data physically stored in the memory module. Conventionally, a secondary memory divided into multiple logical data blocks, each logical data block consisting of a single physical data block or more than one equal-sized physical data blocks representing the smallest readable units of data, is employed, and data requested from said secondary memory are copied to said primary memory when required. When a logical data block in a storage area of the second memory is accessed by a specific process of an application running on the computing device, this logical data block is copied into a designated storage area of said primary memory. In order to save storage capacity of said secondary memory, data to be stored in the secondary memory (e.g., the machine code of a software program to be executed by an application accessing said primary memory and said secondary memory) can be compressed, which can be made transparent to all applications accessing said secondary memory by decompressing these data when copying them to the primary memory. However, the size of the compressed data is unknown, which may cause problems when copying said data. The compressed data can be found by using a pointer (also referred to as “index”) which indicates where compressed logical data blocks start and end, respectively, but the employed compression procedure often (typically, in more than 50% of all cases) causes the compressed logical data blocks to cross physical block boundaries, which makes it necessary to access more of the compressed logical data blocks than necessary to be able to decompress and copy a single logical data block. As known from the prior art, an approach to cope with the above-identified problem is to cache some of these compressed logical data blocks from the secondary memory into the primary memory, but the effectiveness of this approach is unknown.
In most cases, encoded data (e.g., a software machine source code) can be compressed to an amount between 50% and 60% of its original size. If all data blocks to be stored in the secondary memory could be compressed to half their original size, it would be possible to store logical data blocks in form of physical data blocks having half the size of the logical ones (or any integer multiple of that size). This would make an index search redundant and the loading of the encoded data fast. However, this is hardly ever the case.